package now_coder.backtracking;

public class NC109 {

    static class UnionFind{
        protected int[] parents;

        public UnionFind(int n){
            parents = new int[n];
            for (int i = 0; i < parents.length; i++) {
                parents[i] = i;
            }
        }

        public int find(int vert){
            int trail = vert;
            while (parents[vert] != vert){
                vert = parents[vert];
            }
            int root = vert, lead;
            for (int v = trail; v != root; v = lead){
                lead = parents[v];
                parents[v] = root;
            }
            return root;
        }

        public void union(int i, int j){
            int v1 = find(i);
            int v2 = find(j);
            if (v1 != v2){
                parents[v1] = v2;
            }
        }
    }

    private int rows;
    private int cols;

    public int solve (char[][] grid) {
        if (grid == null || grid.length == 0)
            return 0;

        rows = grid.length;
        cols = grid[0].length;
        UnionFind uf = new UnionFind(rows * cols);

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1){
                    if (i + 1 < rows && grid[i + 1][j] == 1)
                        uf.union(node(i, j), node(i + 1, j));
                    if (j + 1 < cols && grid[i][j + 1] == 1)
                        uf.union(node(i, j), node(i, j + 1));
                }
            }
        }

        int counter = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1 && uf.parents[node(i, j)] == node(i, j))
                    counter++;
            }
        }

        return counter;
    }

    private int node(int i, int j){
        return i * cols + j;
    }

    public static void main(String[] args) {
        System.out.println(new NC109().solve(new char[][]{
                {1, 1, 0, 0, 0},
                {0, 1, 0, 1, 1},
                {0, 0, 0, 1, 1},
                {0, 0, 0, 0, 0},
                {0, 0, 1, 1, 1}
        }));
    }

}
